package org.hot100_1;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class leetcode63 {
    public boolean isValid(String s) {

        int n = s.length();
        if ( n%2!=0){
            return false;
        }
        Map<Character,Character> map = new HashMap<>();
        map.put('(',')');
        map.put('[',']');
        map.put('{','}');

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < n; i++) {

            char ch = s.charAt(i);

            //传入的是左括号
            if (map.containsKey(ch)){
                //将对应的右括号放入
                stack.push(map.get(ch));
            }else {
                //传入的是右括号
                //栈为空或者是栈中最新放入的括号与当前的括号不同
                if (stack.isEmpty() || stack.peek()!=ch){
                    return false;
                }
                //栈中最新放入的括号与当前的括号相同，触发弹栈
                stack.pop();
            }
        }

        return stack.isEmpty();
    }
}
